﻿#include"BSTree.h"
//#include"BSTree_val.h"

//
//int main()
//{
//	BsTree<int> bs;
//
//	bs.INSERT(2);
//	bs.INSERT(1);
//	bs.INSERT(3);
//	bs.INSERT(4);
//	bs.INSERT(-1);
//	bs.INSERT(0);
//
//	bs.Inorther();
//
//	if (bs.FIND(11))
//	{
//		cout << "找到了\n";
//	}
//	else
//	{
//		cout << "找不到\n";
//	}
//
//	
//
//	bs.Erase(4);
//	bs.Inorther();
//
//	
//
//	return 0;
//}
//
//int main()
//{
//
//	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "香蕉", "苹果", "西瓜", "苹果"};
//
//	BsTree<string, int> countTree;
//	for (const auto& str : arr)
//	{
//		// 先查找⽔果在不在搜索树中
//		// 1、不在，说明⽔果第⼀次出现，则插⼊<⽔果, 1>
//		// 2、在，则查找到的结点中⽔果对应的次数++
//		//BSTreeNode<string, int>* ret = countTree.Find(str);
//		auto ret = countTree.FIND(str);
//		if (ret == NULL)
//		{
//			countTree.INSERT(str, 1);
//		}
//		else
//		{
//			ret->_value++;
//		}
//	}
//	countTree.Inorther();
//
//	BsTree<string, int> ss;
//	ss = countTree;
//	ss.Inorther();
//
//	return 0;
//}
#include<vector>
class Solution {
public:
    void duplicateZeros(vector<int>& arr) {

        //先找到从后向前遍历的的位置
        int cur = 0;
        int dest = -1;
        while (cur < arr.size())
        {

            if (arr[cur] != 0)
                ++dest;
            else
                dest += 2;

            if (dest >= arr.size() - 1)break;
            cur++;
        }

        //处理边界问题
        if (dest == arr.size())
        {
            arr[dest - 1] = 0;

            cur--;
            dest -= 2;
        }

        for (; cur >= 0; cur--)
        {
            if (arr[cur])arr[dest--] = 0;
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
            }
        }

        // auto it = arr.begin();
        // for (int i = 0; i < arr.size(); i++) {
        //     if (arr[i] == 0) {
        //         arr.insert(it + i, 0);
        //     }
        // }
    }
};

int main()
{
    Solution s;
    s.duplicateZeros();

    return 0;
}